1. Field of the Invention
This invention relates to a method and apparatus for generating pseudorandom numbers and, more particularly, to a method and apparatus for generating pseudorandom numbers in a cryptographic module of a computer system.
2. Description of the Related Art
In many large computer systems, cryptographic functions such as encryption and decryption, key management and the like are offloaded to a special-purpose cryptographic module or facility that is designed to provide an enhanced level of physical security. Applications invoke the cryptographic functions by issuing defined service requests to the cryptographic module.
One of the standard functions performed by a cryptographic module is random number generation, or more precisely pseudorandom number (PRN) generation since the numbers are usually generated by a deterministic process. Pseudorandom numbers may be generated either in the performance of some cryptographic function (such as key management) or in response to a request from an application (such as for an initializing vector) that is performing some cryptographic procedure.
Random number generators can be grouped into two types: true random and pseudorandom. True random number generators are based on some physical noise source of random information, such as alpha particles, output of a zener diode, power supply voltage variations, etc. The generator may use this random noise directly or may use it to control an oscillator. For example, U.S. Pat. No. 4,905,176 to R. A. Schulz, entitled "Random Number Generator Circuit", derives randomness from noise variations in the power supply voltage; these variations are used to control the frequency of a free-running oscillator.
True random number generators are exposed to circuit failures that are not easily detected. It is also difficult, if not impossible, to certify that a true random number generator is actually random and not predictable. This is particularly true for a very large scale integrated (VLSI) chip. It is difficult to guarantee that a free-running oscillator will actually result in a random, rather than a repeatable, pattern. As the manufacturing process gets more accurate, there is a tendency for all chips to operate in the same manner. Also, a VLSI chip may have a tendency to produce the same output each time it is powered up.
Pseudorandom number generators, on the other hand, operate deterministically but produce output values that satisfy various statistical tests of randomness. Pseudorandom number generators may take advantage of the characteristics of digital circuitry to perform error checking. Thus, a failure of the circuitry can easily be detected.
The overall security of a cryptographic module (and thus the system as a whole) is critically dependent on having a cryptographically strong pseudorandom number generation algorithm. By "cryptographically strong" is meant that not only must the values provided meet all the normal tests for statistical randomness, but also, given one or more outputs of the pseudorandom number generator, the work factor to determine previous values or predict future values must be computationally infeasible. Otherwise, an attacker might determine these previous or future values and use them to compromise the security of the system.
This problem of providing a cryptographically strong pseudorandom number generation algorithm has been compounded by recent improvements in integrated circuit technology, which has allowed functions previously performed on multiple interconnected chips to be performed on a single physical chip. As a result of this consolidation, initialization of the pseudorandom number generator becomes a more critical issue. No longer are several asynchronous units tied together. Instead, all the functions are in a single chip. With a single chip containing the entire function, it becomes much more likely that the resultant state after two different initialization sequences will be the same, or at least with some correlation. This is because timings between the various parts of the same chip will have much less variation between one initialization and the next than they did when these units were in different parts of the system with different power sources at different temperatures and with other environmental variations. Also, this consolidation onto a single chip may result in less variation between units. One would expect much less variation between different chips than between systems assembled from multiple units.
Thus, there is an exposure that an attacker can experiment with a particular chip, or with several chips, and be able to predict the approximate state of the pseudorandom number generator after the initialization sequence. This prediction, along with the fact that some of the outputs from the pseudorandom number generator are made publicly available, while others are used for critical secret information, presents a significant exposure to the security of the entire system.
It should be noted that the level of correlation or the accuracy of prediction does not have to be very high to present a problem. In the area of public key cryptography, the work factor required for public keys is measured in terms of MIPS (millions of instructions per second) years. If, as was the case on one previous machine, the state of the pseudorandom number generator is determined by the combination of two asynchronous events measured with a 10-nanosecond clock and the attacker knows the timing of these within a variation of 10 milliseconds, then the total number of states of the pseudorandom number generator is 10.sup.12. If the attacker can compute these at the rate of 10.sup.6 a second, he can find the state in about six days.
D. Abraham et al., "DEA-Based Pseudorandom Number Generator", IBM Technical Disclosure Bulletin, vol. 35, no. 1B, June 1992, pp. 431-434, and D. Abraham et al., "Initialization Procedure for DEA-Based Pseudorandom Number Generator", IBM Technical Disclosure Bulletin, vol. 35, no. 1B, June 1992, pp. 351-353, (hereinafter collectively referred to as "Abraham et al.") describe a pseudorandom number generator designed for use in a cryptographic system.
Abraham et al. generate a 64-bit pseudorandom number (RNDNK) by XORing the outputs of two triple-DES encryption functions operating with respective 128-bit encryption keys; these encryption keys (referred to as seed keys) are generated from a system master key in an initialization procedure. The first encryption function receives as a data input the output of a first counter (ctr) that is incremented each time a request is received for generating a pseudorandom number. The second encryption function receives a data input that depends on the mode of operation. In a first mode, the data input is the same counter output (ctr) used as the data input to the first encryption function. In a second mode, the data input is the output of a counter (ctr1) that is incremented by the system clock.
In their initialization procedure, Abraham et al. first generate a value Y independently of the system master key using a series of iterations, one for each entry of a master key part. On the first iteration, the contents of a 64-bit register reg1 are replaced with eK(reg1), where eK() denotes DES encryption under the key K=hex `55555555 55555555`. On each subsequent iteration before the final iteration, the register contents reg1 are replaced with eK(reg1 XOR ctr1), where ctr1 is the output of a 64-bit counter incremented by the system clock. On the final iteration, the XOR product is used as the output value Y rather than being stored in the register reg1, and the register reg1 is reset to zero. The Y value is used to generate 64-bit parts (k1 left, k1 right, k2 left, k2 right) of the two 128-bit seed keys (K1, K2) as
k1 left=eKM(Y) PA1 k1 right=eKM(Y+1) PA1 k2 left=eKM(Y+2) PA1 K2 right=eKM(Y+3)
where eKM() denotes encryption under the 128-bit system master key KM and+denotes ordinary addition.
Although Abraham et al. claim that their procedure is cryptographically strong, a closer inspection reveals several weaknesses.
Abraham et al. require update of the system master key to initialize the pseudorandom number generator. Initialization of the pseudorandom number generator is thus tied to initialization of the system master key. Therefore, Abraham et al. cannot generate pseudorandom numbers before installation of the first system master key and thus cannot generate the system master key internally (since the key generation process itself requires a random number). Often, however, random numbers are required before a system master key has been installed. Also, Abraham et al. cannot reinitialize the pseudorandom number without changing the system master key.
In addition to these initialization problems, Abraham et al. introduce no new entropy (i.e., randomness) into their pseudorandom number generator after initialization. (There is the entropy of the lack of an exact value of ctr1, but this entropy does not increase over time, so the effect is no new entropy.) In such a system, if an attack "succeeds" (that is, one pseudorandom number is broken), the work factor for all other pseudorandom numbers is essentially zero.
As noted above, the scrambling function used in Abraham et al. is triple DES. This has a weakness in that given a known value for the output and the seed, the input can be directly computed.
Abraham et al. claim that the work factor to cryptanalyze the seed keys is at least as great as that to cryptanalyze the system master key. However, this is not true, as the values used at the output are, as noted above, eKM(Y), eKM(Y+1), eKM(Y+2) and eKM(Y+3). Since Y is only 64 bits, an exhaustive attack requires only 2.sup.64 possible values for Y. This is a work factor of only 2.sup.64, whereas the work factor for the system master key KM is 2.sup.128.
In Abraham et al., for all initializations except perhaps for the first, reg1 and ctr1 are reset to zero. To see the problem this may create, assume that user A has permission to use the crypto facility. User A enters a known system master key in two parts. In this case, since there are no intermediate iterations, the value Y is not even a function of the 64-bit counter ctr1. If user A knows Y and the master key (KM), then K1 and K2 are easily computed. If the second method (using ctr1) is used to generate a random number, ctr can easily be computed given K1, K2, ctr1, and RNDNK. Thus, after determining ctr1, which may be a relatively low work factor, user A can determine the current value of ctr with a work factor of zero. When the crypto facility is turned over to user B, user A still has valuable information about the facility. When B changes the master key, A has approximate information about the value of ctr (which is not reset) and ctr1 (which is reset).
In the Abraham et al. system as described in the above-identified references, when only a two-part system master key is entered, the resulting seed key is completely deterministic with a work factor of zero. Thus, Abraham is subject to an insider trap door attack. This can easily be improved by changing it to use ctr1 in each iteration, however the work factor is still quite low. If we assume that a attacker can estimate the time within 2.sup.10 cycles, then the work factor to find the seed would be 2.sup.20.
Abraham et al. derive their seed keys from internal counter/clock values sampled "at indeterminate times based on independent external events not under the control of an adversary". However, it is not good enough merely to be "not under the control" of an adversary. For the system to be secure, the adversary must not have any information about the time. In general, the adversary will have some information (at least what year, probably what day). As shown above, the work factor here may be less than 2.sup.20.
What is needed, therefore, is a pseudorandom number generator that can be implemented on a single silicon chip, can be initialized with integrity, has a suitably high work factor, and has an algorithm simple enough, yet strong enough, that it can be published. This latter point is important since cryptographic systems are generally more secure when they rely on secret values in known algorithms rather than on the secrecy of the algorithm itself. Often the scrutiny that results from publication can uncover subtle weaknesses in an algorithm that are not immediately apparent.
Another problem with pseudorandom number generators relates to their restoration after power off. Thus, an integrated circuit (IC) chip may implement a pseudorandom number generator in active components which are volatile registers. If system power is removed, the active components are lost and the pseudorandom number generator must be reinitialized. This is undesirable, as initialization requires a considerable amount of time and external cooperation. There are several possible schemes for backing up the working registers to nonvolatile storage as part of normal operation; after a power failure, the working registers can be restored from the nonvolatile storage. However, it turns out that most of these schemes are highly susceptible to replay attacks.
Finally, in a system in which special hardware is used to implement a pseudorandom number generator, special problems are encountered in testing the circuitry that is unique to the pseudorandom number generation process. Many failures that would make the output unacceptable cannot be easily detected.